package com.cat.chapter049;

/**
 * @author cat
 * @description https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/description/
 * @create 2025/7/20 15:08
 * @since JDK17
 */

public class Solution07 {

    public int longestSubstring(String str, int k) {
        char[] s = str.toCharArray();
        int[] h = new int[26];
        int ans = 0, cnt = 0, n = s.length;
        for (int i = 0; i < n; i++) {
            cnt += ++h[s[i] - 'a'] == 1 ? 1 : 0;
        }
        for (int i = 1; i <= cnt; i++) {
            ans = Math.max(ans, f(s, n, k, i));
        }
        return ans;
    }

    public int f(char[] s, int n, int k, int m) {
        int ans = 0, cnt = 0, debt = 0;
        int[] h = new int[126];
        for (int l = 0, r = 0; r < n; r++) {
            cnt += h[s[r]] == 0 ? 1 : 0;
            debt += ++h[s[r]] == k ? 1 : 0;

            while (cnt > m) {
                cnt -= h[s[l]] == 1 ? 1 : 0;    // 少了一种新字符
                debt -= h[s[l++]]-- == k ? 1 : 0;
            }
            if (cnt == m && debt >= m) {
                ans = Math.max(ans, r - l + 1);
            }
        }
        return ans;
    }
}